//2. 两数相加
//思路：1. 把l1与l2的每个节点的值都拿出来相加，将个位上的数字开辟一个节点记下来
//2. 再把进位的值每次都保存下来，并在每次都更新，保证在下一次加的时候是正确的
//这样的方法就可以解决数字过大，没有类型能存的问题

#include <stdio.h>
#include <stdlib.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* BuyListNode(int x) {
	struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (NULL == newnode)
	{
		perror("malloc fail:");
		return NULL;
	}
	newnode->val = x;
	newnode->next = NULL;

	return newnode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	struct ListNode* cur1 = l1, * cur2 = l2;
	int sum = 0, carry = 0;

	sum = cur1->val + cur2->val + carry;
	struct ListNode* head = BuyListNode(sum % 10);
	struct ListNode* prev = head;
	carry = sum / 10;

	cur1 = cur1->next;
	cur2 = cur2->next;
	while (cur1 && cur2)
	{
		sum = cur1->val + cur2->val + carry;
		struct ListNode* newnode = BuyListNode(sum % 10);
		prev->next = newnode;
		prev = newnode;
		carry = sum / 10;

		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	if (cur1 == NULL)
	{
		while (cur2)
		{
			sum = cur2->val + carry;
			struct ListNode* newnode = BuyListNode(sum % 10);
			prev->next = newnode;
			prev = newnode;
			carry = sum / 10;

			cur2 = cur2->next;
		}
	}
	if (cur2 == NULL)
	{
		while (cur1)
		{
			sum = cur1->val + carry;
			struct ListNode* newnode = BuyListNode(sum % 10);
			prev->next = newnode;
			prev = newnode;
			carry = sum / 10;

			cur1 = cur1->next;
		}
	}
	if (carry != 0)
	{
		struct ListNode* newnode = BuyListNode(carry);
		prev->next = newnode;
	}

	return head;
}